#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//按之字形顺序打印二叉树，两个栈分别存储奇数行和偶数行，交替进行
vector<vector<int>> Print(TreeNode *pRoot)
{
    if (!pRoot)
    {
        return {};
    }
    vector<vector<int>> res;
    stack<TreeNode *> s1, s2;
    s1.push(pRoot);
    while (!s1.empty() || !s2.empty())
    {
        vector<int> tmp1;
        while (!s1.empty())
        {
            TreeNode *p = s1.top();
            s1.pop();
            if (p)
            {
                tmp1.push_back(p->val);
                s2.push(p->left);
                s2.push(p->right);
            }
        }
        if (!tmp1.empty())
        {
            res.push_back(tmp1);
        }
        vector<int> tmp2;
        while (!s2.empty())
        {
            TreeNode *p = s2.top();
            s2.pop();
            if (p)
            {
                tmp2.push_back(p->val);
                s1.push(p->right);
                s1.push(p->left);
            }
        }
        if (!tmp2.empty())
        {
            res.push_back(tmp2);
        }
    }
    return res;
}

void test()
{
}

int main()
{
    test();
    return 0;
}